/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package util.sorting;

/**
 * A BST with keys and values both of type int (so that the values can be
 * interpreted as the number of times the key is a member of the set). This
 * includes an interesting 'join' method from Sedgewick, 3rd ed (what is the
 * original source?) This join operation is used in collecting information such
 * as document distribution bottom up.The code using Multimap is easy to
 * understand, as opposed to the rather hacky way that information is collected
 * bottom up in Yamamoto and Church (at least that's my opinion).
 */
import saphre.core.Store;
import util.tokenization_io.BoundarySymbols;

import java.util.List;
import java.util.Set;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
import util.sedgewick.StdStats;

/**
 * 
 * @author Dale Gerdemann
 */
public class Multiset {

    public class Elem implements Comparable<Multiset.Elem> {

        int key_;
        int val_;

        public Elem(int key, int val) {
            key_ = key;
            val_ = val;
        }

        public int getKey() {
            return key_;
        }

        public int getValue() {
            return val_;
        }

        @Override
        public int compareTo(Multiset.Elem other) {
            if (val_ < other.val_) {
                return -1;
            } else if (val_ > other.val_) {
                return 1;
            } else if (key_ < other.key_) {
                return -1;
            } else if (key_ > other.key_) {
                return 1;
            } else {
                return 0;
            }
        }

        public String toString(Store store) {
            return String.format("%10s %10s;", store.toString(key_), val_);
        }
    }

    private class Node {

        int key;
        int val;
        Node l, r;

        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }

        Node(Node other) {
            this.key = other.key;
            this.val = other.val;
            if (other.l != null) {
                this.l = new Node(l);
            }
            if (other.l != null) {
                this.l = new Node(l);
            }
            if (other.r != null) {
                this.r = new Node(r);
            }
        }
    }
    
    private Node head;
    private int size;
    private int cardinality;
    public static Store store;

    public Multiset() {
        size = 0;
        cardinality = 0;
    }

    public Multiset(Multiset other) {
        size = other.size;
        cardinality = other.cardinality;
        head = new Node(other.head);
    }

    /**
     * Size counts the number of different elements. Size of support, written as
     * ↾M↿.
     */
    public int size() {
        return size;
    }

    /**
     * Cardinality counts all elements, including duplicates.
     */
    public int cardinality() {
        return cardinality;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int[] cnts(Set<Integer> keys) {
        int[] result = new int[keys.size()];
        int i = 0;
        for (int k : keys) {
            result[i++] = cnt(head, k);
        }
        return result;
    }

    public int cnt(int key) {
        return cnt(head, key);
    }

    private int cnt(Node h, int key) {
        if (h == null) {
            return 0;
        }
        if (key < h.key) {
            return cnt(h.l, key);
        }
        if (key > h.key) {
            return cnt(h.r, key);
        }
        return h.val;
    }

    public int[] valArray() {
        List<Integer> result0 = new ArrayList<Integer>();
        valArray(head, result0);
        int[] result = new int[result0.size()];
        for (int i = 0; i < result0.size(); i++) {
            result[i] = result0.get(i);
        }
        return result;
    }

    public void valArray(Node h, List<Integer> v) {
        if (h != null) {
            valArray(h.l, v);
            v.add(h.val);
            valArray(h.r, v);
        }
    }

    public double stddev() {
        int[] v = valArray();
        double[] v2 = new double[v.length];
        for (int i = 0; i < v.length; i++) {
            v2[i] = v[i];
        }
        return StdStats.stddev(v2);
    }

    public List<Multiset.Elem> asList() {
        List<Multiset.Elem> result = new ArrayList<Multiset.Elem>();
        asList(head, result);
        Collections.sort(result);
        return result;
    }

    public void asList(Node h, List<Multiset.Elem> v) {
        if (h != null) {
            asList(h.l, v);
            v.add(new Multiset.Elem(h.key, h.val));
            asList(h.r, v);
        }
    }

    public void addTo(Multiset v) {
        addTo(head, v);
    }

    public void addTo(Node h, Multiset v) {
        if (h != null) {
            addTo(h.l, v);
            int val = v.cnt(h.key);
            v.insert(h.key, h.val);
            addTo(h.r, v);
        }
    }

    public int numSingletons(BoundarySymbols tc) {
        return numSingletons(head, 0, tc);
    }

    private int numSingletons(Node h, int acc0, BoundarySymbols tc) {
        if (h == null) {
            return acc0;
        } else {
            int acc1 = numSingletons(h.l, acc0, tc);
            if (h.val == 1) {
                acc1++;
            } else if (tc.userSentinel(h.key)) {
                acc1 += h.val;
            }
            return numSingletons(h.r, acc1, tc);
        }
    }

    public int getSingleton(BoundarySymbols tc) {
        return getSingleton(head, tc);
    }

    private int getSingleton(Node h, BoundarySymbols tc) {
        if (h == null) {
            return -1;
        }
        if (h.val == 1) {
            return h.key;
        }
        int key = getSingleton(h.l, tc);
        if (key != -1) {
            return key;
        }
        key = getSingleton(h.r, tc);
        if (key != -1) {
            return key;
        }
        return -1;
    }

    private Node insertR(Node h, int key, int val) {
        if (h == null) {
            return new Node(key, val);
        }
        if (key < h.key) {
            h.l = insertR(h.l, key, val);
        } else if (key > h.key) {
            h.r = insertR(h.r, key, val);
        } else {
            size--;
            h.val += val;
        }
        return h;
    }

    private Node multiplyR(Node h, int factor) {
        if (h == null) {
            return null;
        }
        h = new Node(h.key, factor * h.val);
        h.l = multiplyR(h.l, factor);
        h.r = multiplyR(h.l, factor);
        return h;
    }

    public void multiply(int factor) {
        cardinality *= factor;
        head = multiplyR(head, factor);
    }

    public void insert(int key, int val) {
        // size is tentatively incremented. 
        // If key was already in the Multiset
        // then size will be decremented again
        size++;
        cardinality += val;
        head = insertR(head, key, val);
    }

    public void insert(Multiset other) {
        insert(other.head);
    }

    private void insert(Node h) {
        if (h != null) {
            insert(h.l);
            insert(h.key, h.val);
            insert(h.r);
        }
    }

    public void incr(int key) {
        insert(key, 1);
    }

    public void incrAll() {
        incrAll(head);
    }

    public void incrAll(Node h) {
        if (h != null) {
            incrAll(h.l);
            h.val++;
            incrAll(h.r);
        }
    }

    private Node rotR(Node h) {
        Node x = h.l;
        h.l = x.r;
        x.r = h;
        return x;
    }

    private Node rotL(Node h) {
        Node x = h.r;
        h.r = x.l;
        x.l = h;
        return x;
    }

    private Node insertT(Node h, int key, int val) {
        if (h == null) {
            return new Node(key, val);
        }
        if (key < h.key) {
            h.l = insertT(h.l, key, val);
            h = rotR(h);
        } else if (key > h.key) {
            h.r = insertT(h.r, key, val);
            h = rotL(h);
        } else {
            size--;
            h.val += val;
        }
        return h;
    }

    public void insertT(int key, int val) {
        head = insertT(head, key, val);
    }

    private Node joinR(Node a, Node b) {
        if (b == null) {
            return a;
        }
        if (a == null) {
            return b;
        }
        b = insertT(b, a.key, a.val);
        b.l = joinR(a.l, b.l);
        b.r = joinR(a.r, b.r);
        return b;
    }

    public void join(Multiset b) {
        size += b.size;
        cardinality += b.cardinality;
        head = joinR(head, b.head);
    }

    private static void toDebugString(String tab, Node h, StringBuilder sb) {
        if (h != null) {
            toDebugString(tab + "  ", h.r, sb);
            if (h.val != 0) {
                sb.append(tab + h.key + ":" + h.val + '\n');
            }
            toDebugString(tab + "  ", h.l, sb);
        }
    }

    public String toDebugString() {
        StringBuilder sb = new StringBuilder();
        toDebugString("", head, sb);
        return sb.toString();
    }

    private static void toString(Node h, StringBuilder sb) {
        if (h != null) {
            toString(h.l, sb);
            if (h.val != 0) {
                sb.append("(" + h.key + "," + h.val + "),");
            }
            toString(h.r, sb);
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('{');
        toString(head, sb);
        if (sb.length() == 1) {
            sb.append(" ");
        }
        if (sb.length() > 0) {
            sb.setCharAt(sb.length() - 1, '}');
        }
        return sb.toString();
    }

    private static void toString(String[] cpat, Node h, StringBuilder sb,
            String sentinel) {
        if (h != null) {
            String w = h.key < cpat.length ? cpat[h.key] : sentinel;


            toString(cpat, h.l, sb, sentinel);
            if (h.val != 0) {
                sb.append("(" + w + "," + h.val + "),");
            }
            toString(cpat, h.r, sb, sentinel);
        }
    }

    public String toString(Store store, int idx) {
        StringBuilder sb = new StringBuilder();
        toString(store, idx, head, sb);
        if (sb.length() == 1) {
            sb.append(" ");
        }
        if (sb.length() > 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }

    private static void toString(Store store, int idx, Node h,
            StringBuilder sb) {
        if (h != null) {
            String w = store.toString(idx, idx + h.key);
            //String w = h.key < cpat.length ? cpat[h.key] : sentinel;
            toString(store, idx, h.l, sb);
            if (h.val != 0) {
                sb.append("(" + w + "," + h.val + "),");
            }
            toString(store, idx, h.r, sb);
        }
    }

    /**
     * A toString method with names supplied by the Store
     *
     * @param cpat the source of names substituted for the ints
     * @return a string representation
     */
    public String toString(String[] cpat, String sentinel) {
        StringBuilder sb = new StringBuilder();
        sb.append('{');
        toString(cpat, head, sb, sentinel);
        if (sb.length() == 1) {
            sb.append(" ");
        }
        sb.setCharAt(sb.length() - 1, '}');
        return sb.toString();
    }

    /**
     *
     */
    public String toString(String[] cpat, String sentinel, int lo, int hi) {
        StringBuilder sb = new StringBuilder();
        sb.append('{');
        toString(cpat, head, sb, sentinel, lo, hi);
        if (sb.length() == 1) {
            sb.append(" ");
        }
        sb.setCharAt(sb.length() - 1, '}');
        return sb.toString();
    }

    private static void toString(String[] cpat, Node h, StringBuilder sb,
            String sentinel, int lo, int hi) {
        if (h != null) {
            String w = h.key < cpat.length ? cpat[h.key] : sentinel;


            toString(cpat, h.l, sb, sentinel, lo, hi);
            if (h.val != 0 && h.val >= lo && h.val <= hi) {
                sb.append("(" + w + "," + h.val + "),");
            }
            toString(cpat, h.r, sb, sentinel, lo, hi);
        }
    }

    private static void toStringDF(Store store, Node h, StringBuilder sb) {
        if (h != null) {
            toStringDF(store, h.l, sb);
            if (h.val != 0) {
                sb.append("(" + store.docName(h.key) + "," + h.val + "),");
            }
            toStringDF(store, h.r, sb);
        }
    }

    /**
     * A toString method with names supplied by the Store
     *
     * @param store the source of names substituted for the ints
     * @return a string representation
     */
    public String toStringDF(Store store) {
        StringBuilder sb = new StringBuilder();
        sb.append('{');
        toStringDF(store, head, sb);
        if (sb.length() == 1) {
            sb.append(" ");
        }
        sb.setCharAt(sb.length() - 1, '}');
        return sb.toString();
    }

    private static void toStringDFSupport(Store store, Node h, StringBuilder sb) {
        if (h != null) {
            toStringDFSupport(store, h.l, sb);
            sb.append(store.docName(h.key) + ",");
            toStringDFSupport(store, h.r, sb);
        }
    }

    /**
     * A toString method with names supplied by the Store
     *
     * @param store the source of names substituted for the ints
     * @return a string representation
     */
    public String toStringDFSupport(Store store) {
        StringBuilder sb = new StringBuilder();
        sb.append('{');
        toStringDFSupport(store, head, sb);
        if (sb.length() == 1) {
            sb.append(" ");
        }
        sb.setCharAt(sb.length() - 1, '}');
        return sb.toString();
    }

    private static void toStringWF(Store store, Node h, StringBuilder sb) {
        if (h != null) {
            toStringWF(store, h.l, sb);
            if (h.val != 0) {
                sb.append("(" + store.toString(h.key) + ":" + h.val + "),");
            }
            toStringWF(store, h.r, sb);
        }
    }

    /**
     * A toString method with names supplied by the Store
     *
     * @param store the source of names substituted for the ints
     * @return a string representation
     */
    public String toStringWF(Store store) {
        StringBuilder sb = new StringBuilder();
        sb.append('{');
        toStringWF(store, head, sb);
        if (sb.length() == 1) {
            sb.append(" ");
        }
        sb.setCharAt(sb.length() - 1, '}');
        return sb.toString();
    }

    private static void toStringWFSupport(Store store, Node h,
            StringBuilder sb) {
        if (h != null) {
            toStringWFSupport(store, h.l, sb);
            sb.append(store.toString(h.key) + ",,,");
            toStringWFSupport(store, h.r, sb);
        }
    }

    /**
     * A toString method with names supplied by the Store
     *
     * @param store the source of names substituted for the ints
     * @return a string representation
     */
    public String toStringWFSupport(Store store) {
        StringBuilder sb = new StringBuilder();
        sb.append('{');
        toStringWFSupport(store, head, sb);
        if (sb.length() == 1) {
            sb.append(" ");
        }
        sb.setCharAt(sb.length() - 1, '}');
        return sb.toString();
    }

    public List<Integer> support() {
        List<Integer> result = new ArrayList<Integer>();
        support(head, result);
        return result;

    }

    private void support(Node head, List<Integer> result) {
        if (head == null) {
            return;
        }
        if (head.val > 0) {
            result.add(head.key);
        }
        support(head.l, result);
        support(head.r, result);
    }

    /**
     * Method to get all members of the multiset with number of occurrences
     * above a specified threshold.
     *
     * @param head starting node
     * @param lo the threshold
     * @param vals a secondary return; <code>val.get(i)==n</code> ⟺ i is n times
     * a member of the Multiset, where n is a number greater than or equal
     * to <code>lo</code>.
     * @return the list of integers with number of occurrences above the
     * threshold (<code>lo</lo>).
     */
    public List<Integer> freqGreater(int lo, List<Integer> vals) {
        List<Integer> result = new ArrayList<Integer>();
        freqGreater(head, lo, result, vals);
        return result;
    }

    /**
     * Private helper method.
     *
     * @param head starting node
     * @param lo the threshold
     * @param result a collector for results
     */
    private void freqGreater(Node head, int lo, List<Integer> result,
            List<Integer> vals) {
        if (head == null) {
            return;
        }
        if (head.val >= lo) {
            result.add(head.key);
            vals.add(head.val);
        }
        freqGreater(head.l, lo, result, vals);
        freqGreater(head.r, lo, result, vals);
    }

    public static void main(String[] args) {

        Multiset a = new Multiset();
        Random r = new Random();
        for (int i = 0; i < 16; i++) {
            int k = r.nextInt(10);
            System.out.println(k);
            a.incr(k);
        }

        System.out.println(a.toString());

        /*
         int[] a1 = {13, 9, 18};
         Multiset a = new Multiset();
         for (int docID : a1) {
         a.incr(docID);
         }

         int[] b1 = {8, 13, 1};
         Multiset b = new Multiset();
         for (int docID : b1) {
         b.incr(docID);
         }

         System.out.println("before:\n" + a + "\n-----------\n" + b);
         a.join(b);
         System.out.println("after:\n" + a + "\n-----------\n" + b);
         */

        System.out.println("size: " + a.size());
        System.out.println("cardinality: " + a.cardinality());

    }
}
